public class LowestCommonAncestor {
    // leetcode 二叉树的最近公共祖先
    // https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked

    /**
     * 对于一棵树如何判断给出的节点的最近公共祖先，对于root节点来说
     * 1. 如果root为p或q其中一个，那么root激就是最近公共祖先
     * 2. 如果root的左子树和右子树都出现了公共祖先，那其实就是节点本身是自己的祖先，那么p和q的最近公共性祖先就是root
     * 3. 如果左子树存在公共祖先，但是右子树不存在，那么最近公共祖先就是左子树的最近公共祖先
     * 4. 反之就是右子树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode leftParent = lowestCommonAncestor(root.left, p, q);
        TreeNode rightParent = lowestCommonAncestor(root.right, p, q);
        if (leftParent != null && rightParent != null) return root;
        if (leftParent == null) return rightParent;
        return leftParent;
    }
}
